Improved Tag Set Design and Multiplexing Algorithms for Universal Arrays

摘要

In this paper we address two optimization problems arising in the design ofgenomic assays based on universal tag arrays. First, we address the universalarray tag set design problem. For this problem, we extend previous formulationsto incorporate antitag-to-antitag hybridization constraints in addition toconstraints on antitag-to-tag hybridization specificity, establish aconstructive upper bound on the maximum number of tags satisfying the extendedconstraints, and propose a simple greedy tag selection algorithm. Second, wegive methods for improving the multiplexing rate in large-scale genomic assaysby combining primer selection with tag assignment. Experimental results onsimulated data show that this integrated optimization leads to reductions of upto 50% in the number of required arrays.